package com.leetcode;

public class AddTwoNumbers {

	public static void main(String[] args) {
//		ListNode l1 = new ListNode(2);
//		l1.next = new ListNode(4);
//		l1.next.next = new ListNode(3);
//		l1.next.next.next = null;
//		ListNode l2 = new ListNode(5);
//		l2.next = new ListNode(6);
//		l2.next.next = new ListNode(4);
//		l2.next.next.next = null;
		 ListNode l1 = new ListNode(1);
		 l1.next = new ListNode(8);
		 ListNode l2 = new ListNode(0);
		printListNode(l1);
		printListNode(l2);
		// ����l1+l2
		ListNode l3 = addTwoNumbers(l1, l2);
		printListNode(l3);

	}

	public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		ListNode l3 = new ListNode(0);
		ListNode cur = l3;
		int carry = 0; // ��λ
		int v1 = 0, v2 = 0;
		while (l1 != null || l2 != null) {
			v1 = l1 == null ? 0 : l1.val;
			v2 = l2 == null ? 0 : l2.val;
			cur.val += v1 + v2;
			carry = cur.val / 10;
			cur.val = cur.val % 10;

			l1 = l1 == null ? l1 : l1.next;
			l2 = l2 == null ? l2 : l2.next;
			if (l1 == null && l2 == null&&carry==0) {
				break;
			}else{
				cur.next = new ListNode(carry);
				cur = cur.next;
			}

		}
		return l3;
	}

	/**
	 * �������
	 * @param l
	 */
	public static void printListNode(ListNode l) {
		while (l != null) {
			if (l.next != null) {
				System.out.print(l.val + "->");
			} else {
				System.out.println(l.val);
			}
			l = l.next;
		}
	}

	public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
		ListNode head = new ListNode(0);
		ListNode copy = head;
		int carry = 0;
		int sum = 0;
		int v1 = 0;
		int v2 = 0;
		while (l1 != null || l2 != null || carry != 0) {
			v1 = l1 == null ? 0 : l1.val;
			v2 = l2 == null ? 0 : l2.val;
			sum = v1 + v2 + carry >= 10 ? v1 + v2 + carry - 10 : v1 + v2 + carry;
			copy.next = new ListNode(sum);
			carry = v1 + v2 + carry >= 10 ? 1 : 0;
			l1 = l1 == null ? l1 : l1.next;
			l2 = l2 == null ? l2 : l2.next;
			copy = copy.next;
		}
		return head.next;
	}

	public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
		ListNode pre = new ListNode(0);
		ListNode curr = pre;
		int carry = 0;
		while (l1 != null || l2 != null || carry != 0) {
			int v1 = l1 == null ? 0 : l1.val;
			int v2 = l2 == null ? 0 : l2.val;
			int sum = v1 + v2 + carry;
			carry = sum / 10;
			curr.next = new ListNode(sum % 10);
			curr = curr.next;
			l1 = l1 == null ? l1 : l1.next;
			l2 = l2 == null ? l2 : l2.next;
		}
		return pre.next;
	}

}

//class ListNode {
//	int val;
//	ListNode next;
//
//	ListNode(int x) {
//		val = x;
//	}
//}